iT邦幫忙

2021 iThome 鐵人賽

DAY 3
1
Software Development

少女人妻在廚房裡想不通的演算法系列 第 3

【在廚房想30天的演算法】Day 03 那個時間複雜度會讓人生變複雜嗎?

  • 分享至 

  • xImage
  •  

Aloha!又是我少女人妻Uerica!話說這次有很多以前的朋友同學們一起參加鐵人賽,,不但可以一起加油打氣,因為每天都會去收看大家的文章,真是收穫滿滿~啊。


常見的時間複雜度

延續昨日的嫩煎雞翅,大致說明了一下時間複雜度評估與判斷的方式和概念。但通常哪種程式碼的演算法是比較有效率的呢?先來看一下這張圖!x軸為執行時間、y軸為輸入資料量

rUDdxlb

圖片引用自 : http://bigocheatsheet.com/

圖示可見除非確定輸入資料量 (n) 很小,不然一般不建議使用指數階或階乘時間複雜度的演算法 (圖示的紅色區塊)。


實際範例

以下範例均將 n 訂為 10, x 值表示執行幾次。

常數階 O(1)
將 a, b 的值交換,無論 a, b 值中的數字多大都不影響步驟數。

let a = 10;
let b = 20;
let temp = a;
a = b;
b = temp;  

對數階 O(log n)
在下列 while 迴圈中的例子,i 每次進入迴圈都會乘 2 ,直到 i 值大於 n 為止,表示 2 的 x 次方大於 n 迴圈才會停止,而 x 值代表執行了幾次,n 值越大會讓步驟越多、執行時間越長。在 Big O 表示法的 log n 的底數因是常數,影響不大所以可省略。

2 ^ x = n
x = log2 n
= O( log n )

let i = 1;
let n = 10;
let x = 0;
while ( i < n ) {
    i = i * 2;
    x++ // 執行 1 次加 1
}
console.log (x); // 4

線性階 O(n)
下面例子中,程式執行的時間會隨著迴圈內的 n 做增加,其餘部分則不會受太多影響。

let n = 10;
let x = 0
for ( let i = 1 ; i <= n ; i++ ){
    x++;
};
console.log (x); // 10

線性對數階 O(n * log n)
O(n * log n)與前面說的對數階 O(log n) 相似,在外包一層for迴圈,使 n 個循環次數乘上 log n

let n = 10;
let x = 0;
for (let i = 1 ; i <= n ; i++){
    let j = 1;
    while (j < n) {
        j = j * 2;
        x++;
    }
}
console.log (x); // 40

平方階 O(n^2)
以前做題目最愛用的雙迴圈,竟然是紅色警戒區(嚇到吃手手),顧名思義就是迴圈內再跑一個迴圈,資料量若會成長則不建議使用!

let x = 0;
let n = 10;
for (let i = 1 ; i <= n ; i++){
    for (let i = 1 ; i <= n ; i++){
        x++;
    };
};
console.log (x); // 100

參考資料:

[資料結構] 演算法評估與資料型別

時間複雜度和空間複雜度,大 O 表示法【數據結構和算法入門2】


好的~今天就先到這邊啦!明天再談空間複雜度吧!晚安掰掰!


上一篇
【在廚房想30天的演算法】Day 02 想著想著想到一個 Big O
下一篇
【在廚房想30天的演算法】Day 04 來淺談一下空間複雜度
系列文
少女人妻在廚房裡想不通的演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言